package leetcode_101_120;

import utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class maxDepth_104 {
    /**
     *给定一个二叉树 root ，返回其最大深度。
     * 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        dfs(root);
        return maxDepth;
    }
    int k=0;
    int maxDepth=0;
    void dfs(TreeNode node) {
        k++;  //进入下一层就加1
        if(node==null){
            maxDepth = Integer.max(k-1, maxDepth);
            return;
        }
        dfs(node.left);
        k--;  //从左孩子回来就减1
        dfs(node.right);
        k--; //同理
    }

    /**
     * 评论区简洁高效写法
     * 每一层找出左右子树更深的哪一个加一往上层递归送
     * @param root
     * @return
     */
    public int maxDepth2(TreeNode root) {
        return root == null ? 0 : Math.max(maxDepth2(root.left), maxDepth2(root.right)) + 1;
    }
}
